package com.ronz.recursion;

/**
 * @Description 八皇后问题
 *              八皇后问题， 是一个古老而著名的问题， 是回溯算法的典型案例。 该问题是国际西洋棋棋手马克斯· 贝瑟尔于
 *              1848 年提出： 在 8× 8 格的国际象棋上摆放八个皇后， 使其不能互相攻击， 即： 任意两个皇后都不能处于同一行、
 *              同一列或同一斜线上， 问有多少种摆法(共有92种)。
 * @Author Ronz
 * @Date 2021/1/4 11:00
 * @Version 1.0
 */
public class No3_Recursion_EightQueens {

    private static int max = 8;             // 总共 8 个皇后
    private static int[] arr = new int[8];  // 这个一维数组用于存放8个皇后在棋盘的摆放位置，索引代表行，值代表列

    private static int num = 0;

    public static void main(String[] args) {
        // 从第 0 行，开始摆放
        check(0);
        System.out.printf("最终解法有：%d 种", num);
    }

    /**
     * @Description 开始摆放皇后
     * @Param [n] 当前准备摆放的皇后的索引值（也就是所在行数）
     * @return void
     */
    public static void check(int n){
        // 递归首先是退出条件，也就是第 8 个皇后摆放完毕，即开始摆放第 9 个皇后了，就说明成功了
        if (n == max){
            // 摆放完毕，就打印一下吧
            num++;      // 记录下成功的次数
            showArr();
            return;
        }
        // 如果不符合退出条件
        // 因为每一个皇后在每一行的摆放位置都有 8 个可能，所以需要遍历 8 次
        for (int i=0; i<max; i++){
            arr[n] = i;     // 摆放
            // 判断摆放是否合理
            if (isReasonable(n)){
                // 摆放合理的话，就开始摆放下一个
                check(n+1);
            }
        }

    }

    /**
     * @Description 判断当前摆放的皇后是否和之前摆放的皇后有冲突
     * @Param [n] 当前正在摆放的皇后的索引值
     */
    public static boolean isReasonable(int n){
        // 需要遍历，也就是和前面的每一个皇后进行比对当前摆放位置是否合理
        for (int i=0; i<n; i++){
            // arr[i] == arr[n] 代表的是摆放在同一列
            // Math.abs(n -i) == Math.abs(arr[n] - arr[i]) 代表的是摆放在对角线上
            if (arr[i] == arr[n] || Math.abs(n -i) == Math.abs(arr[n] - arr[i])){
                return false;
            }
        }
        return true;
    }

    /**
     * @Description 打印数组
     */
    public static void showArr(){
        for (int i=0; i<max; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
